Multiplication of binary numbers is a common requirement in implementing various functions using Programmable Logic Devices (PLD). It is therefore desirable to have an efficient and fast multiplication capability. Neither the configurable logic cells of existing designs of PLDs are designed for multiplication nor are the multiplication schemes proposed according to PLD architectures. This limitation is described in context of the complete multiplication process outlined below.
In the basic binary multiplication process, each bit of the multiplier beginning with the Least Significant bit (LSB) is examined in turn. If the multiplier bit is a “1”, the current value of the multiplicand is added to the partial product result. If the multiplier bit is a “0”, then the current value of the multiplicand is not added to the result. After each addition step, the multiplicand is shifted left by one bit in preparation for the next operation. The multiplication may either be carried out serially for each bit, or in parallel for all bits simultaneously. In a PLD, the conditional sum and multiplicand shifting are carried out by an array of interconnected logic cells, each of which operates on a single bit of the multiplicand and a single bit of the multiplier. The condition check of the multiplicand in a logic cell is achieved by an AND function and the addition operation is performed by a 1-bit Full Adder.
The basic multiplication operation therefore requires the output of the ANDing of the multiplicand and the multiplier to be added to the input carry and the input partial product. The output from the multiplication of the multiplicand by each bit of the multiplier except the final bit multiplication is termed as “Partial Product”. The 1-bit Full Adder receives a 1-bit carry input from the previous bit stage in the same bit multiplication as an addition input and also generates a 1-bit carry output for the next stage. Each bit multiplication extends over multiple multiplier “cells” with each cell providing product of a single bit of the multiplicand with a single bit of the multiplier. A “row” of such multiplier cells provide “Partial Product” of the multiplicand with one bit of the multiplier.
In parallel multipliers, a plurality of rows (as many as the number of bits in the multiplicand) is connected in a cascade manner. The “Partial Product” output from a row is connected to the input of the next row in a bit-shifted fashion to form a 2-dimensional matrix of cells. For providing optimal speed of operation, it is essential to minimize circuit delays in the path of both the partial product term and the carry input and carry output terms.
The “basic cell” of a parallel multiplier consists of an AND gate receiving one bit of the multiplier and the multiplicand at its input, and its output is coupled to a 1-bit full adder. The full adder also receives the partial product from the previous stage and the carry input from the previous bit position. The output of the full adder serves as the partial product for the next stage or as product bit of the final binary product. The multiplication of one bit of the multiplier with all the bits of the multiplicand results in the generation of partial product output that forms the input for the multiplication of the next bit of the multiplier with the shifted value of the multiplicand.
FIG. 1 shows the block diagram of a parallel multiplier illustrating the cascaded arrangement of cells. The multiplier array 1.1 comprises of multiple individual Configurable Logic Cells (CLCS) 1.2 interconnected in a staggered row and column matrix. The multiplicand 1.3 provides the bit inputs for the columns of the matrix while the multiplier 1.4 provides the bit inputs for the rows of the matrix. Each CLC 1.2 receives a single multiplicand bit input 1.5, a single multiplier bit input 1.6, a Partial Product bit input 1.9 and a Carry-In bit input 1.7. Each multiplier bit is connected to the multiplier bit inputs of all the CLCs in a row i.e. multiplier bit 1.6 is connected to all the CLC's 1.2 of the first row. Each multiplicand bit is connected to the multiplicand bit inputs of CLCs in a bit-shifted manner, precisely, multiplicand bit 1.5 is connected to first CLC's of all the rows which in turn are shifted one position from the previous CLC. Each CLC provides two outputs, a Partial Product output 1.10 and a Carry Out bit 1.8. The Partial Product Output 1.10 is connected to the partial Product Input 1.9 of the CLC of the subsequent row in the same column while the carry out 1.8 is connected to the Carry In 1.7 of the adjacent CLC on the left in the same row. The output can be tapped from the output terminals 1.11 to 1.n. 
FIG. 2 shows the internal functional structure of a single CLC 2.1 in multiplication mode. A multiplicand bit 2.2 and a multiplier bit 2.3 are connected to the two inputs of a two-input AND gate 2.8. The output of the AND gate provides the conditional addition input 2.10 of the multiplicand to one input of one-bit Full Adder 2.9. The other input of the Full Adder is connected to Partial Product input bit 2.5. The Full Adder 2.9 computes the Partial Product output bit 2.6, which is the sum of Partial Product input 2.5, Carry In 2.4 and conditional multiplicand bit input 2.10, and also generates a Carry Out bit 2.7.
The aforesaid structure requires two CLBs for its implementation in a FPGA as one CLB is utilized for implementing a full adder while the other is utilized for implementing AND gate functionality. Thus lot of hardware is involved for multiplying two bits.
A multiplier structure is required to utilize PLD resources efficiently and a CLC is thus desired that efficiently implements the basic multiplier cell without the introduction of overheads in hardware. The proposed method implements the multiplier without using AND gate at the input of Adder. Further the proposed multiplier cell can be directly implemented in a CLC by the mapping the full adder and a partial product generator in a single CLC.
The proposed CLC architecture can be implemented in United States Patent Publication No. 2002/0116426 entitled “Look-up table apparatus to perform two-bit arithmetic operation including carry generation”.